//给你一个整数 c，表示 c 个电站，每个电站有一个唯一标识符 id，从 1 到 c 编号。 
//
// 这些电站通过 n 条 双向 电缆互相连接，表示为一个二维数组 connections，其中每个元素 connections[i] = [ui, vi] 表
//示电站 ui 和电站 vi 之间的连接。直接或间接连接的电站组成了一个 电网 。 
//
// 最初，所有 电站均处于在线（正常运行）状态。 
//
// 另给你一个二维数组 queries，其中每个查询属于以下 两种类型之一 ： 
//
// 
// [1, x]：请求对电站 x 进行维护检查。如果电站 x 在线，则它自行解决检查。如果电站 x 已离线，则检查由与 x 同一 电网 中 编号最小 的在线电
//站解决。如果该电网中 不存在 任何 在线 电站，则返回 -1。 
// [2, x]：电站 x 离线（即变为非运行状态）。 
// 
//
// 返回一个整数数组，表示按照查询中出现的顺序，所有类型为 [1, x] 的查询结果。 
//
// 注意：电网的结构是固定的；离线（非运行）的节点仍然属于其所在的电网，且离线操作不会改变电网的连接性。 
//
// 
//
// 示例 1： 
//
// 
// 输入： c = 5, connections = [[1,2],[2,3],[3,4],[4,5]], queries = [[1,3],[2,1],[1
//,1],[2,2],[1,2]] 
// 
//
// 输出： [3,2,3] 
//
// 解释： 
//
// 
//
// 
// 最初，所有电站 {1, 2, 3, 4, 5} 都在线，并组成一个电网。 
// 查询 [1,3]：电站 3 在线，因此维护检查由电站 3 自行解决。 
// 查询 [2,1]：电站 1 离线。剩余在线电站为 {2, 3, 4, 5}。 
// 查询 [1,1]：电站 1 离线，因此检查由电网中编号最小的在线电站解决，即电站 2。 
// 查询 [2,2]：电站 2 离线。剩余在线电站为 {3, 4, 5}。 
// 查询 [1,2]：电站 2 离线，因此检查由电网中编号最小的在线电站解决，即电站 3。 
// 
//
// 示例 2： 
//
// 
// 输入： c = 3, connections = [], queries = [[1,1],[2,1],[1,1]] 
// 
//
// 输出： [1,-1] 
//
// 解释： 
//
// 
// 没有连接，因此每个电站是一个独立的电网。 
// 查询 [1,1]：电站 1 在线，且属于其独立电网，因此维护检查由电站 1 自行解决。 
// 查询 [2,1]：电站 1 离线。 
// 查询 [1,1]：电站 1 离线，且其电网中没有其他电站，因此结果为 -1。 
// 
//
// 
//
// 提示： 
//
// 
// 1 <= c <= 10⁵ 
// 0 <= n == connections.length <= min(10⁵, c * (c - 1) / 2) 
// connections[i].length == 2 
// 1 <= ui, vi <= c 
// ui != vi 
// 1 <= queries.length <= 2 * 10⁵ 
// queries[i].length == 2 
// queries[i][0] 为 1 或 2。 
// 1 <= queries[i][1] <= c 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 数组 哈希表 有序集合 堆（优先队列） 👍 27 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author ldltd
 * @date 2025-11-06 14:19:10
 * @description 3607.电网维护
 */
public class PowerGridMaintenance{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 PowerGridMaintenance fun=new PowerGridMaintenance();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //  1.离线请求后，会影响后面的查询吗？会
	     //  2.最临近的节点如果是离线的怎么办？ 继续往下找
	// 因为一开始构建后，整个图是不变的，所以可以用并查集来维护连通分量

	/*
	方法一：懒删除堆
	首先，建图 + DFS，把每个连通块中的节点加到各自的最小堆中。每个最小堆维护对应连通块的节点编号。
然后处理询问。
对于类型二，用一个 offline 布尔数组表示离线的电站。这一步不修改堆。
对于类型一：
如果电站 x 在线，那么答案为 x。
否则检查 x 所处堆的堆顶是否在线。若离线，则弹出堆顶，重复该过程。如果堆为不空，那么答案为堆顶，否则为 −1。
为了找到 x 所属的堆，还需要一个数组 belong 记录每个节点在哪个堆中。
*/
		 public int[] processQueries1(int c, int[][] connections, int[][] queries) {
			 List<Integer>[] g = new ArrayList[c + 1];
			 // 构件图
			 Arrays.setAll(g, i -> new ArrayList<>());
			 for (int[] e : connections) {
				 int x = e[0], y = e[1];
				 g[x].add(y);
				 g[y].add(x);
			 }
			 // 记录堆的归属
			 int[] belong = new int[c + 1];
			 Arrays.fill(belong, -1);
			 List<PriorityQueue<Integer>> heaps = new ArrayList<>();
			 PriorityQueue<Integer> pq;
			 for (int i = 1; i <= c; i++) {
				 // 如果已经记录过了，跳过
				 if (belong[i] >= 0) {
					 continue;
				 }
				 pq = new PriorityQueue<>();
				 dfs(i, g, belong, heaps.size(), pq);
				 heaps.add(pq);
			 }

			 int ansSize = 0;
			 for (int[] q : queries) {
				 // q==2的标识下线，只需要返回q==1的结果
				 if (q[0] == 1) {
					 ansSize++;
				 }
			 }

			 int[] ans = new int[ansSize];
			 int idx = 0;
			 // 离线电站
			 boolean[] offline = new boolean[c + 1];
			 for (int[] q : queries) {
				 int x = q[1];
				 if (q[0] == 2) {
					 offline[x] = true;
					 continue;
				 }
				 if (!offline[x]) {
					 ans[idx++] = x;
					 continue;
				 }
				 pq = heaps.get(belong[x]);
				 // 懒删除：取堆顶的时候，如果离线，才删除
				 while (!pq.isEmpty() && offline[pq.peek()]) {
					 pq.poll();
				 }
				 ans[idx++] = pq.isEmpty() ? -1 : pq.peek();
			 }
			 return ans;
		 }

	private void dfs(int x, List<Integer>[] g, int[] belong, int compId, PriorityQueue<Integer> pq) {
		belong[x] = compId; // 记录节点 x 在哪个堆
		pq.offer(x);
		for (int y : g[x]) {
			if (belong[y] < 0) {
				dfs(y, g, belong, compId, pq);
			}
		}
	}
		 /*方法二：倒序处理 + 维护最小值
倒序处理询问，离线变成在线，删除变成添加，每个连通块只需要一个 int 变量就可以维护最小值。
注意可能存在同一个节点多次离线的情况，我们需要记录节点离线的最早时间（询问的下标）。对于倒序处理来说，离线的最早时间才是真正的在线时间。
*/
	public int[] processQueries(int c, int[][] connections, int[][] queries) {
		List<Integer>[] g = new ArrayList[c + 1];
		Arrays.setAll(g, i -> new ArrayList<>());
		for (int[] e : connections) {
			int x = e[0], y = e[1];
			g[x].add(y);
			g[y].add(x);
		}

		int[] belong = new int[c + 1];
		Arrays.fill(belong, -1);
		int cc = 0; // 连通块编号
		for (int i = 1; i <= c; i++) {
			if (belong[i] < 0) {
				dfs(i, g, belong, cc);
				cc++;
			}
		}

		int[] offlineTime = new int[c + 1];
		Arrays.fill(offlineTime, Integer.MAX_VALUE);
		int q1 = 0;
		for (int i = queries.length - 1; i >= 0; i--) {
			int[] q = queries[i];
			if (q[0] == 2) {
				offlineTime[q[1]] = i; // 记录最早离线时间
			} else {
				q1++;
			}
		}

		// 维护每个连通块的在线电站的最小编号
		int[] mn = new int[cc];
		Arrays.fill(mn, Integer.MAX_VALUE);
		for (int i = 1; i <= c; i++) {
			if (offlineTime[i] == Integer.MAX_VALUE) { // 最终仍然在线
				int j = belong[i];
				mn[j] = Math.min(mn[j], i);
			}
		}

		int[] ans = new int[q1];
		for (int i = queries.length - 1; i >= 0; i--) {
			int[] q = queries[i];
			int x = q[1];
			int j = belong[x];
			if (q[0] == 2) {
				if (offlineTime[x] == i) { // 变回在线,因为是倒序记录的最早的，在那之前是在线的
					// 此时更新连通块的最小值为 当前值 和 记录最小值 的较小值
					mn[j] = Math.min(mn[j], x);
				}
				// 在线查询
			} else {
				q1--;
				if (i < offlineTime[x]) { // 已经在线（写 < 或者 <= 都可以），直接返回 x
					ans[q1] = x;
				} else if (mn[j] != Integer.MAX_VALUE) { // 离线则取连通块的最小值
					ans[q1] = mn[j];
				} else { // 连通块没有在线电站
					ans[q1] = -1;
				}
			}
		}
		return ans;
	}
	private void dfs(int x, List<Integer>[] g, int[] belong, int compId) {
		belong[x] = compId;
		for (int y : g[x]) {
			if (belong[y] < 0) {
				dfs(y, g, belong, compId);
			}
		}
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
